Trie 1[入门]

无内鬼，来点入门级题目。
Trie就不讲了，只讲题。

一点无关紧要但是可能引起阅读障碍的点：
①tot的初值到底啥情况，怎么一会$1$一会$0$的
答：tot的最开始的初值是根节点$root$，具体在分配新的$id$的时候，是用的前置$++$，故最开始的$tot$的初值是没有显明分配的，但是具体在$Trei$的操作里初始的点位置必须是根节点，如果不对应会出错。一会$1$一会$0$是因为有些代码是我以前的，后来新写的时候没注意这个问题，不过不影响。
②#define _CRT_SECURE_NO_WARNINGS是什么
答：关闭$msvc$的检查，不影响。

①Hdu 4825 Xor Sum
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4825
题目大意：给定一个$n$个数的集合，一共有$m$次询问，每次询问给出一个数$x$，问在集合里与$x$异或后结果最大的数是哪一个。
数据范围：
$1 \leq N,M \leq 10^5$
所有正整数均在$int$范围内。
分析：把所有的数看成是$2$进制数插入$Trie$中，每次查询时如果有与当前$x$的一个数位上相反的数字，就选择相反的，没有就只能退而求其次选择与这一位相同的。
不过本题是要输出原来的数字，故$search$时，如果当前走下去的那一位是$1$的话，就把$res$里的这一个数位调整成1，最后输出$res$即可。
代码：

using namespace std;

const int N = 1e5+7;
int trie[N*32][2],tot = 1,tar[N * 32];
int a[N];
void insert(int a)
{
    int p = 1;
    for(int i = 31;i >= 0;--i)
    {
        int ch = a >> i & 1;
        if(!trie[p][ch])    trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    tar[p] = a;
}
int search(int x)
{
    int p = 1,res = 0;
    for(int i = 31;i >= 0;--i)
    {
        int ch = x >> i & 1;
        if(trie[p][ch ^ 1])	p = trie[p][ch ^ 1],res += (!ch) ? (1 << i) : 0;
        else p = trie[p][ch],res += (ch) ? (1 << i) : 0;
    }
    return tar[p];
}
int main()
{
	int T;scanf("%d",&T);
	for(int _ = 1;_ <= T;++_)
	{
		memset(trie,0,sizeof trie);
		memset(tar,0,sizeof tar);
		tot = 1;
		printf("Case #%d:\n",_);
		int n,m;scanf("%d%d",&n,&m);
	    for(int i = 0;i < n;++i)
	    {
	        scanf("%d",&a[i]);
	        insert(a[i]);
	    }
	    for(int i = 0;i < m;++i)
	    {
	    	int x;scanf("%d",&x);
	    	printf("%d\n",search(x));
	    }
	}

    return 0;
}

②Hdu 5536 Chip Factory
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5536
题目大意：给定一个$n$个数的集合$\{a\}$，求下式

$\max\limits_{i \neq j ,j \neq k,k \neq i} (a_i + a_j) \bigoplus (a_k)$

数据范围：
$3 \leq n \leq 1000$
$0 \leq a_i \leq 10^9$
分析：
题目意思就是在集合里选出三个数，求一下两个和和另外一个数的异或。这个题很显然就不能像上面那样直接去把所有数丢进$Trie$再$search$推答案了，但是呢由于$n$很小，所以时间上允许我们枚举每个数对丢到$Trie$里查找答案，故一个比较直接的想法就是想办法实现在$Trie$中删除掉某个字符串。先把所有单个的数$a_i$加入$Trie$，再枚举所有数对的时候，先把数对里的两个数从$Trie$里删除，再查询两者的和在$Trie$里最大的结果具体是多少。
现在来考虑怎么删除掉$Trie$中的一个字符串。很显然直接把$Trie$里的下标，或者说指针的指向给他删掉是不可取的，可以采取标记的措施：对每个分配了位置的具体的节点，加一个$cnt$记录他一共有几次被使用上了，$insert$的时候就$+1$，$delete$的时候就$-1$。最后在具体$search$的时候，不光要看下一个节点是否存在，还要看下一个点的具体$cnt$是不是大于$0$的。
本题范围有点大，记得开$ll$。
代码：

using namespace std;
typedef long long ll;
#define int ll 
const int N = 2007;
int tr[N * 32][2],cnt[N * 32],tot,val[N * 32];
int n,a[N];
void insert(int x,int v)
{
	int p = 0;
	for(int i = 32;i >= 0;--i)
	{
		int ch = x >> i & 1;
		if(!tr[p][ch])	tr[p][ch] = ++tot;
		cnt[tr[p][ch]] += v;
		p = tr[p][ch];
	}
	val[p] = x;
}
int search(int x)
{
	int p = 0;
	for(int i = 32;i >= 0;--i)
	{
		int ch = x >> i & 1;
		if(tr[p][ch ^ 1])	
		{
			if(cnt[tr[p][ch ^ 1]] > 0)
				p = tr[p][ch ^ 1];
			else
				p = tr[p][ch];
		}
		else
			p = tr[p][ch];
	}
	return val[p];
}
void update(int x,int v)
{
	int p = 0;
	for(int i = 32;i >= 0;--i)
	{
		int ch = x >> i & 1;
		cnt[tr[p][ch]] += v;
		p = tr[p][ch];
	}
}
signed main()
{
	int T;scanf("%lld",&T);
	while(T--)
	{
		memset(tr,0,sizeof tr);
		memset(val,0,sizeof val);
		memset(cnt,0,sizeof cnt);
		tot = 0;
		scanf("%lld",&n);
		for(int i = 1;i <= n;++i)	scanf("%lld",&a[i]),insert(a[i],1);
		int res = 0;
		for(int i = 1;i <= n;++i)
		{
			for(int j = i + 1;j <= n;++j)
			{
				update(a[j],-1);update(a[i],-1);
				res = max(res,search(a[i] + a[j]) ^ (a[i] + a[j]));
				update(a[j],1);update(a[i],1);
			}
		}
		printf("%lld\n",res);
	}


    return 0;
}

③洛谷4551 最长异或路径
原题链接：https://www.luogu.com.cn/problem/P4551
题目大意：给定一颗$n$个节点的树，下标从$1$到$n$。在树上找到两个不同的节点求最长的异或路径，即经过的路径上的所有权值的异或和。
分析：
如果说这个题不是异或和，而是普通的加和，我们很容易想到应该是合并两两段最大的往下的路径和。但是异或很显然是没有说两个最大的结果异或起来是最大的结果这样的特性，我们只能退而求其次。找到从根节点往下的所有节点的路径异或和，即求出一个$D[x]$为$root$到$x$的简单路径的异或和。之后相当于在树上找另外一个节点$y$，使得$D[x] \bigoplus D[y]$的结果最大，这显然用$Trie$就可以实现了。
而且在$search$的时候，其实不需要在意$x \neq y$的条件，一个是不可能只有D{x]自己，第二个是就算所有序列里都是$D[x]$，这个时候查到的其他的$y$虽然值与之相等但是不同的数，也不违反规则。
代码：

using namespace std;

const int N = 1e5+7,M = 2e6+7;
int trie[N*32][2],a[N],tot = 1;
int edge[M],cost[M],ver[M],succ[M],cnt;
void add(int u,int v,int w)
{
    edge[cnt] = v;
    cost[cnt] = w;
    succ[cnt] = ver[u];
    ver[u] = cnt++;
}
void dfs(int u,int fa,int sum)
{
    a[u] = sum;
    for(int i = ver[u];~i;i = succ[i])
    {
        int j = edge[i];
        if(j != fa) dfs(j,u,sum^cost[i]);
    }
}
void insert(int a)
{
    int p = 1;
    for(int i = 31;i >= 0;--i)
    {
        int ch = a >> i & 1;
        if(!trie[p][ch])    trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
}
int search(int a)
{
    int res = 0,p = 1;
    for(int i = 31;i >= 0;--i)
    {
        int ch = a >> i & 1;
        if(trie[p][ch^1])
            res |= (1 << i),p = trie[p][ch^1];
        else p = trie[p][ch];
    }
    return res;
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    memset(ver,-1,sizeof(ver));
    int n;cin >> n;
    for(int i = 0;i < n-1;++i)
    {
        int u,v,w;cin >> u >> v >> w;
        --u;--v;
        add(u,v,w);
        add(v,u,w);
    }
    dfs(0,-1,0);
    int res = 0;
    for(int i = 0;i < n;++i)
        insert(a[i]);
    for(int i = 0;i < n;++i)
        res = max(res,search(a[i]));
    cout << res;
    return 0;
}